package ch5.part10;

/**
 * 大正整数相加
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class BigNumberSum {

    /**
     * 每位都是1位数
     * 时间复杂度：O(n) = n
     *
     * @param strA 大整数A
     * @param strB 大整数B
     * @return 加和结果
     */
    private static String bigNumberSum(String strA, String strB) {

        // 1. 构建A、B数组，注意是逆序构建，这样正好位对齐
        int length = strA.length() > strB.length() ? strA.length() : strB.length();
        int[] numA = new int[length + 1];
        for (int i = 0, len = strA.length(); i < len; i++) {
            numA[i] = strA.charAt(len - i - 1) - '0';
        }
        int[] numB = new int[length + 1];
        for (int i = 0, len = strB.length(); i < len; i++) {
            numB[i] = strB.charAt(len - i - 1) - '0';
        }
        int[] numS = new int[length + 1];

        // 2. 遍历A、B数组，此处为顺序运算，正好是个位和个位运算
        int result;
        for (int i = 0; i < length; i++) {
            result = numA[i] + numB[i] + numS[i];
            if (result >= 10) {
                numS[i] = result - 10;
                numS[i + 1] = numS[i + 1] + 1;
            } else {
                numS[i] = result;
            }
        }

        // 3. 基于Sum的数组，构建String
        StringBuilder builder = new StringBuilder(length);
        for (int i = length - 1; i >= 0; i--) {
            if (numS[i] == 0 && i == length - 1) {
                continue;
            }
            builder.append(numS[i]);
        }
        return builder.toString();
    }

    /**
     * 循环次数要较上一方法减少8/9，但是内部逻辑不太好理解了就
     *
     * @param strA 大整数A
     * @param strB 大整数B
     * @return 加和结果
     */
    private static String bigNumberSumV9(String strA, String strB) {
        // 1. 构建A、B数组，注意是逆序构建，这样正好位对齐
        int length = strA.length() > strB.length() ? strA.length() : strB.length();
        int arrayLength = (length + 1) / 9 + 1;
        int start, end;
        String subStr;

        int[] numA = new int[arrayLength];
        int[] numB = new int[arrayLength];
        int[] numS = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {
            start = strA.length() - (i + 1) * 9;
            start = start >= 0 ? start : 0;
            end = strA.length() - i * 9;
            end = end >= 0 ? end : 0;
            subStr = strA.substring(start, end);
            subStr = "".equals(subStr) ? "0" : subStr;
            numA[i] = Integer.valueOf(subStr);

            start = strB.length() - (i + 1) * 9;
            start = start >= 0 ? start : 0;
            end = strB.length() - i * 9;
            end = end >= 0 ? end : 0;
            subStr = strB.substring(start, end);
            subStr = "".equals(subStr) ? "0" : subStr;
            numB[i] = Integer.valueOf(subStr);
        }


        // 2. 遍历A、B数组，此处为顺序运算，正好是个位和个位运算
        int result;
        for (int i = 0; i < arrayLength; i++) {
            result = numA[i] + numB[i] + numS[i];
            if (result >= 1000000000) {
                numS[i] = result - 1000000000;
                numS[i + 1] = numS[i + 1] + 1;
            } else {
                numS[i] = result;
            }
        }

        // 3. 基于Sum的数组，构建String
        StringBuilder builder = new StringBuilder(length + 1);
        for (int i = arrayLength - 1; i >= 0; i--) {
            if (numS[i] == 0 && i == arrayLength - 1) {
                continue;
            }
            builder.append(numS[i]);
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        System.out.println(bigNumberSum("426709752318", "95481253129"));
        System.out.println(bigNumberSum("745325426709752318", "34567395481253129"));
        System.out.println(bigNumberSumV9("426709752318", "95481253129"));
        System.out.println(bigNumberSumV9("745325426709752318", "34567395481253129"));
    }

}